COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Notes for keynoter, LISP conference
C00008 00003	.require "memo.pub[let,jmc]" source
C00012 00004		LISP is an approximate local optimum among programming
C00013 00005	.bb Improvements
C00017 00006	.bb Complaints
C00018 00007	.bb Mysteries
C00021 00008	Abstract: LISP has survived for 21 years because it is
C00022 ENDMK
C⊗;
Notes for keynoter, LISP conference

1. variant of history paper, especially administrative history with
evaluation of advantages and disadvantages of what happened.

2. proposals for improvements

	the language itself

	can LISP be the universal language

	higher than LISP preserving self-reference (making the idea precise)

	libraries as part of the system and documented

	organizing and financing a computerized LISP library center

	what standardization is possible

	non-toy LISP on micros is possible

	proving programs and other theory 

Open questions

	lazy eval

	higher order objects

3. criticism of the LISP machine as the forefront

	LISP seems, after Fortran, to be the second oldest surviving
programming language and seems even less likely than Fortran to
be superseded in the near future.  Consider the following attempts
to displace it:

	1. SLIP included list processing in Fortran.  It used
bidirectional lists and didn't allow recursive functions or
conditional expressions.  The bidirectional lists offered
advantages in only a few applications but otherwise took up
space and time.  It didn't encourage on-line use, since Fortran
doesn't.

	2. Formac was another Fortran based language that was pushed
for a while by part of IBM.  It was dedicated to manipulating
a class of algebraic formulas written in Fortran style and was also
oriented to batch processing.

	3. Formula Algol was dedicated to the linguistic pun
that the elementary operations can be regarded as operating
on numbers or on formulas.  The idea was that if a variable
⊗x has no value, then operations on expressions involving
⊗x must be regarded as operating on the formula.  A few programs
could be written, but the pun proved an inadequate basis for
substantial programs.

	4. Perhaps the most interesting rival to LISP is (or was)
POP-2.  It has everything that LISP has except that its
statements are written in an Algol-like form and don't have
any list structure internal form.  Thus POP-2 programs can
produce other POP-2 programs only as character strings.
.require "memo.pub[let,jmc]" source
.cb LISP - PAST AND FUTURE


	I'm not sure what I should say on LISP's approximate 21st
anniversary - no doubt something could be said about coming of age, but it
seems doubtful that the normal life expectancy of a programming language
is three score and ten.  In fact, LISP seems to be the second oldest
surviving programming language after Fortran, so maybe we should plan on
giving it a gold watch.  I could talk about the good old days, the early
history of LISP, but I already gave a paper on that subject at the ACM
conference on the history of programming languages.

	I think I'll review the salient features of LISP, discuss the
reasons for its long survival, discuss its peculiar history of never being
supported by a computer company, grumble about a few practices I find
distasteful,
make some remarks on proving LISP programs correct,
discuss how some organized efforts that
might make the use of LISP more convenient, and discuss some possible
improvements in the current implementations.  Finally, I will discuss the
prospects for replacing LISP by something substantially better.

	As a programming language, LISP is characterized by the following
ideas:

	#. computing with symbolic expressions rather than numbers

	#. representation of symbolic expressions and other information by
list structure in computer memory

	#. representation of information in on paper, from keyboards
and in other external media mostly by
multi-level lists and sometimes by S-expressions

	#. a small set of selector and constructor
operations expressed as functions, i.e. ⊗car, ⊗cdr and ⊗cons 

	#. composition of functions as a tool for
forming more complex functions

	#. the use of conditional expressions for
getting branching into function definitions

	#. the recursive use of
conditional expressions as a sufficient tool for building computable
functions

	#. the use of λ-expressions for naming functions

	#. the storage of information on the property lists of atoms

	#. the representation of LISP programs as LISP data

	#. the conditional expression interpretation of Boolean connectives

	#. the LISP function %2eval%1 that
serves both as a formal definition of the language and as an interpreter

	#. garbage collection as the means of erasure

	#. LISP statements as a command language in a time-sharing environment

	LISP is an approximate local optimum among programming
languages.  Minor improvements could be made, but they mightn't
be worth the trouble of conversion.  An improvement worth suffering
for might involve the following:
	
.item←0
	#. a higher level way of referring to symbolic information.
Basing the language on pattern matching is the obvious candidate,
but none of the pattern matching languages dev
.bb Improvements

.item←0
	#. Incorporating more standard functions into the language.

	Designers of programming languages often propose omitting
from the definition of the language facilities that can be defined
within the language on the grounds that the user can do it for
himself.  The result is often that users cannot use each others
programs, because each installation and user performs various
common tasks in different ways.  In so far as programmers use
local libraries without rewriting the functions, they are using
different languages if they use different local libraries.  Compatibility
between users of LISP would be much enhanced if there were more
standard functions.

	#. Syntax directed input and output.

	A notation for representing symbolic information can be optimized
from three points of view:  One can try to make it easy to write.
One can try to make it easy and pleasant to read.  One can make
easy to manipulate with computer programs.   Unfortunately, these
desiderata are almost always grossly incompatible.  LISP owes most
of its success to optimizing the third.   LISP lists and S-expressions
in which the ⊗car of an item identifies its kind have proved most
suitable as data for programming.
When the amount of input and output is small, users are inclined to
accept the inconvenience of entering the input and seeing the output
as lists or S-expressions.  Otherwise they write ⊗read and ⊗print programs
of varying elaborateness.  Input and output programs are often a large part
of the work and a major source of bugs.  Moreover, input programs often
must detect and report errors in the syntax of input.

	LISP would be much improved by standard facilities for syntax
directed input and output.  Some years ago Lynn Quam implemented a
system that used the same syntax description for both input and output,
but this was rather constraining.  Probably one wants different
syntaxes for input and output, and input syntaxes should specify
ways of complaining about errors.  The idea is to provide standard
facilities for a programmer to describe correspondences
between data in an external medium and S-expressions, e.g. he should
be able to say something like

	%2(PLUS x1 ... xn) → x1 + ... + xn,

	(DIFFERENCE x y) → x - y%1,

although I hold no brief for this particular notation.
.bb Complaints

.item←0
	#. While pure LISP and the "program feature" extension of
it have a mathematical character that welcomes formalization
and admits reasonable proofs of program properties, many recent
extensions to various versions of LISP are just as ad hoc as the
features of COBOL.  When program proving becomes an accepted
technique, these features will have to be scrapped.
.bb Mysteries

	Several generalizations of LISP features have been proposed
and some have been implemented whose status seems to me to be mysterious.
On the one hand, they seem to be powerful generalizations, and on the other,
it isn't clear that they will be much used in the kind of programming that
is actually done.  Sometimes their consequences for implementation are
difficult to foresee, and the mathematical theory required to prove
the correctness of programs using these features is unavailable.

	#. Daniel Friedman and David Wise have argued that ⊗cons should
not evaluate its arguments and have shown that this allows certain
infinite list structures to be regarded as objects.  Trouble is
avoided, because only as much of the infinite structure is created as
is necessary to get the answers to be printed.  Exactly what domain
of infinite list structures is assumed is unclear to me.

	#. Many people have proposed that full lambda calculus be
implemented.  This would permit higher type functions, i.e. functions
of functions of functions etc., but allows only manipulations based
on composition and lambda conversions, not general manipulations
of their symbolic form.  Even conditional expressions can be imitated
by writing %3true%1 as ⊗λx_y.x, %3false%1 as ⊗λx_y.y and
%2qif_p_qthen_a_qelse_b%1 as ⊗p(a)(b).  The mystery is whether this
has any practical significance, and the current best guess is no.
Abstract: LISP has survived for 21 years because it is
an approximate local optimum in the space of programming
languages.  However, it has accumulated some barnacles
that should be scraped off, and some long-standing
opportunities for improvement have been neglected.
It would benefit from some co-operative maintenance
especially in creating and maintaining program libraries.
Major changes will be required when program proving
becomes widely available.